// gaz.treestore.js - a jQuery-based library to manage trees
//
//   Copyright © 2007 Studio Associato Di Nunzio e Di Gregorio
//
//   Authors:
//      Federico Di Gregorio <fog@initd.org>
//      Pierluidi Di Nunzio  <gg@initd.org>
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU Lesser General Public Licenseas published by
// the Free Software Foundation, either version 3 of the License, or (at 
// your option) any later version. See the file Documentation/LGPL3 in the
// original distribution for details. There is ABSOLUTELY NO warranty.

;(function($) {
    var Gaz = window.Gaz || (window.Gaz = {});
    
    /* A couple of private utility functions */

    function copysort(func, data, src) {
        var dst = [];
        for (var i=src.length-1 ; i >= 0 ; i--)
            dst[i] = src[i];
        if (func)
            dst.sort(function(a, b) { return func(a, b, data); });
        return dst;
    }
    
    function simplify(old, data) {
        var result = [];
        
        function simplify_merge(node) {
            for (var i = result.length-1 ; i >= 0 ; i--) {
                // If the node is a duplicate just drop it.
                if (result[i] === node) {
                    node = null;
                    break;
                }
                
                // First check and remove all nodes that are children of the passed one.
                if (result[i].level > node.level && node.isParent(result[i])) {
                    result.splice(i, 1);
                    continue;
                }

                // Then add the node only if it does not have any parent in list (we
                // don't add it directly but instead just set it to zero and check later.
                if (node.level > result[i].level && result[i].isParent(node)) {
                    node = null;
                    break;
                }
            }
            
            if (node) result.push(node);
        }
        
        for (var i = old.length-1 ; i >= 0 ; i--)
            simplify_merge(old[i]);
        for (var i = data.length-1 ; i >= 0 ; i--)
            simplify_merge(data[i]);

        return result;
    }
    
    
    /* TreeNode function/class */
    
    $.extend(Gaz, {
        TreeNode: function(obj, nodeId) {
            return new Gaz.TreeNode.instance(obj, nodeId);
        }
    });
    
    Gaz.TreeNode.instance = function(obj, nodeId) {
            this.data = obj || null;
            this.id = nodeId || null;
            this.parent = null;
            this.children = [];
            this.level = -1;
            
            return this;
    };
      
    $.extend(Gaz.TreeNode.instance.prototype,
    {
        isRoot: function() {
            return this.parent == null;
        },
        
        isParent: function(child) {
            while (child) {
                if (child.parent === this)
                    return true;
                child = child.parent;
            }
            return false;
        },
        
        addChild: function(node) {
            if (node.parent != this) {
                node.parent = this;
                this.children.push(node);
            }
            return this;
        },

        removeChild: function(node) {
            if (node.parent == this) {
                node.parent = null;
                this.children.splice(this.children.indexOf(node), 1);
            }
            return this;
        },

        moveChild: function(newParent, node) {
            if (node.parent == this && node.parent != newParent) {
                this.removeChild(node);
                newParent.addChild(node);
            }
            return this;
        },

        replaceChild: function(oldNode, newNode) {
            if (oldNode.parent == this) {
                this.removeChild(oldNode).addChild(newNode);
            }
            return this;
        }
    });
    
    /* TreeStore function/class */

    $.extend(Gaz, {
        TreeStore: function(ajax, nodeIdColumn, parentIdColumn, options) {
            return new Gaz.TreeStore.instance(ajax, nodeIdColumn, parentIdColumn, options)
        }
    });

    $.extend(Gaz.TreeStore, {
        FILTER_INCLUDE_NODE: 1,
        FILTER_INCLUDE_SUBTREE: 2,
        
        // some useful shortcuts
        FILTER_NONE: 0,
        FILTER_EXCLUDE_NODE: 2,
        FILTER_EXCLUDE_SUBTREE: 1,
        FILTER_ALL: 3
    });
    
    Gaz.TreeStore.instance = function(nodeIdColumn, parentIdColumn, root, options) {
        this.nodeIdColumn = nodeIdColumn;
        this.parentIdColumn = parentIdColumn;
        
        this.options = $.extend({
            nodeCacheSize: 8
        }, options);
        
        this.nodeCacheSize = this.options.nodeCacheSize;

        // Empty the store without emitting an event during setup.
        this.eventFreezeCount = -1;
        this.empty(root);
        this.eventFreezeCount = 0;
    };

    $.extend(Gaz.TreeStore.instance.prototype,
    {
        empty: function(root) {
            this.count = 0;
            this.root = root || Gaz.TreeNode();

            // Event stack for stopEvents() and startEvents() methods.
            this.eventFreezeCount = 0;
            this.eventFreezeStack = {};

            this.nodeCache = [];     
            
            // Clear client data bacause .empty() invalidates it completely.
            for (var key in this) {
                if (key.match(/_client_/))
                    this[key] = {};
            }
            
            this.triggerTreeChanged(null);
        },
        
        // Method: load
        // Load a dataset (array of objects) into the tree.
        
        load: function(dataset) {
            var self = this;
            
            // First of all we load the new nodes into a new root. Note that
            // to be sure to populate all levels of the tree we need an iterative
            // procedure that goes on until the root is stabilized and the number
            // of nodes without a parent does not change. The following function
            // does the elementary operation of looking for a good place in the
            // tree starting from the given root.
            
            function putNode(root, node, reorder) {
                var moved = false;
                var parentId = node.data[self.parentIdColumn];
                
                // Search for direct children of this node still attached to the root
                // and move them from the root to this node to build the tree faster.
                if (reorder) {
                    for (var i=root.children.length-1 ; i >= 0 ; i--) {
                        var child = root.children[i];
                        if (child.data != null && child.data[self.parentIdColumn] == node.id) {
                            root.moveChild(node, child);
                            moved = true;
                        }
                    }
                }
                
                // Search for a parent of this node in the tree and append it there
                // or to the root if the parent is not available. Note the little
                // optimization where we cache the previous node and we suppose it can
                // be the parent or a sibling of the current node.
                
                var parent;
                if (!parentId)
                    parent = root;
                else if (last.id == parentId)
                    parent = last;
                else if (last.parent && last.parent.id == parentId)
                    parent = last.parent;
                else
                    // You're thinking about removing that "|| root", eh? It just won't work
                    // and the demonstration is left to the reader.
                    parent = self.findNodeById(parentId, root) || root;

                if (node.parent != parent) {
                    parent.addChild(node);
                    last  = node;
                    moved = true;
                }
                
                return moved;
            }
                        
            var root = Gaz.TreeNode();
            var last = root;

            // The first iteration will move all nodes from the dataset to the tree.
            // Also note that we clear the node cache because the first set of operation
            // is on the temporary tree not on the real one.
            
            this.nodeCache.length = 0;this.nodeCache.length = 0;
            
            for (var i=0 ; i < dataset.length; i++) {
                var data = dataset[i];
                var nodeId = data[this.nodeIdColumn];
                var node = Gaz.TreeNode(data, nodeId);
                putNode(root, node, true);
            }

            // Then we iterate until the number of nodes in the root is stable.
            // FIXME: This probably is not necessary. We need to demonstrate it
            // mathematically and then remove the commented code. em is the
            // fresher from studies so it is work for him. <g>
            
            /*var moved = true;
            while (moved == true) {
                moved = false;
                for (var i=root.children.length-1 ; i >= 0 ; i--) {
                    if (putNode(root, root.children[i], true))
                        moved = true;
                }
            }*/
            
            // Here we try to place the full sub-trees that were built into
            // the real tree, replacing nodes with the same id if found. Also,
            // before operating on the real tree we need to clear the cache again.

            this.nodeCache.length = 0;
            
            var replacements = [];
            
            // Save in replacements that an old node with the same id if exists.
            /*for (var i=0 ; i < root.children.length ; i++) {
                var node = root.children[i];
                var old = this.findNodeById(nodeId);
                if (old)
                    replacements.push([old, node]);
            }

            // Append to parent or to root.
            for (var i=0 ; i < root.children.length ; i++) {
                var parent = this.findNodeById(node.data[this.parentIdColumn]) || this.root;
                parent.addChild(node);
            }

            // Replace saved nodes (this is done after everything else to avoid
            // adding extra nodes to be walked by the find methods.
            for (var i=0 ; i < replacements.length ; i++) {
                var r = replacements[i];
                r[0].parent.replaceChild(r[0], r[1]);                
            }*/
            
            var eventData = [];
            
            for (var i=root.children.length-1 ; i >= 0 ; i--) {
                var node = root.children[i];
                var old = this.findNodeById(node.id);
                if (old) {
                    // This allows for sending the same node twice in the same load().
                    // if (old.id == node.id) continue;
                    old.parent.replaceChild(old, node);
                }
                else {
                    var parent = this.findNodeById(node.data[this.parentIdColumn]) || this.root;
                    parent.addChild(node);
                }
                
                if (eventData.indexOf(node.parent) == -1)
                    eventData.push(node.parent);
            }

            this.nodeCache.length = 0;
            
            // And finally we calculate the cached tree level for every node and
            // then emit the 'tree-changed' event with the changed roots as data.
            
            this.count = 0;
            this.each(function(node, tree) {
                node.level = node.parent.level + 1;
                tree.count++;
            }, this);

            this.triggerTreeChanged(eventData);
            
            return this;
        },
        
        moveNodeCheck: function(node, newParent)
        {
            if (node === newParent || node.parent === newParent)
                return false;
                
            // Now the slow part of the function, chech every child of node to
            // be sure we don't create a loop by using it as a parent.
            
            return this.find(function(n) { return n === newParent; }, null, node) == null;
        },
        
        moveNode: function(node, newParent) {
            var oldParent = node.parent;
            if (!newParent)
                newParent = this.root;
            this.nodeCache.length = 0;

            // Detach note from old parent and make sure all event listeners
            // have an option to update (this needs to be done in two steps because
            // the listeners could be not smart enought for a single update.)
            oldParent.removeChild(node);
            this.triggerTreeChanged([oldParent]);

            // Add the node to the new parent and propagate change to listeners.
            node.level = newParent.level + 1;
            newParent.addChild(node);
            this.triggerTreeChanged([newParent]);
            
            return this;
        },
        
        // Method: getRows
        // Calculate a "view" of the tree and return it as plain rows.
        
        getRows: function(fsort, ffilter, fback, data, subtreeId, extraLevel) {
            var result = [];
            
            // The default filter: just hide the root because it's usually fake.
            ffilter = ffilter || function(node, data) { return node.parent != null ? 3 : 2; };
                        
            // The basic algorithm for gathering nodes in the right order goes as follow:
            // 1) filter current node and check result:
            //    1a) if filter returned INCLUDE inlude node and go on (2)
            //    1b) if filter returned EXCLUDE go on (2)
            //    1c) if filter returned EXCLUDE_SUBTREE return
            // 2) get children array and copy it while sorting
            // 3) recursively descend into the children array passing the current
            //    row to allow back propagation of children data (like the number
            //    of filtered-in children)
            
            function gather(node, parent) {
                var fr = ffilter(node, data);
                if (fr & Gaz.TreeStore.FILTER_INCLUDE_NODE) {
                    result.push(node);
                    // Propagate some data about this children back to its parent.
                    if (fback) fback(parent, node, data);
                }
                if (fr & Gaz.TreeStore.FILTER_INCLUDE_SUBTREE) {
                    if (node.children.length > 0) {
                        var children = copysort(fsort, data, node.children);
                        for (var i=0 ; i < children.length ; i++)
                            gather(children[i], node);
                    }
                }
            }
            gather(subtreeId ? this.findNodeById(subtreeId) : this.root);

            return result;
        },

        // Method: findNodeById
        // Search the tree for a node with the given id.
        
        findNodeById : function(nodeId, root) {
            for (var i=0 ; i < this.nodeCache.length ; i++)
                if (this.nodeCache[i].id == nodeId) return this.nodeCache[i];
                
            var result = this.find(function(node) {
                return node.id == nodeId;
            }, null, root);
            
            if (result) {
                this.nodeCache.push(result);
                if (this.nodeCache.length > this.nodeCacheSize)
                    this.nodeCache.shift();
            }
            
            return result;
        },
        
        // Method: createClientData
        // Create a dictionary that will hold client-specific data. This is usefull
        // especially for views that will store client-specific information (like
        // which nodes are expanded) that will be resident accross node changes and
        // reloads. This method also creates four closures to set and retrieve
        // client-specific data about a node and about the whole tree.
        
        createClientData: function(id, obj) {
            var data = this["_client_"+id] = {}
            
            return $.extend(obj || {}, {
                rowGet: function(node, key) {
                    return data[key+node.id];
                },
                
                rowSet: function(node, key, value) {
                    data[key+node.id] = value;
                },
                
                clientGet: function(key) {
                    return data["_client_"+key];
                },
                
                clientSet: function(key, value) {
                    data["_client_"+key] = value;
                }
            });
        },

        removeClientData: function(id, obj) {
            delete this["_client_"+id];
            if (obj) {
                delete obj.rowGet;
                delete obj.rowSet;
                delete obj.clientGet;
                delete obj.clientSet;
            }
        },
        
        triggerTreeChanged: function(rows) {
            this.emitEvent('tree-changed', rows || [this.root], simplify);
        },
        
        stopEvents: function() {
            this.eventFreezeCount += 1;
        },
        
        startEvents: function() {
            this.eventFreezeCount -= 1;

            if (this.eventFreezeCount == 0)
                this.emitEvents();
            
            // If the client called us too much times we simply reset the counter to
            // zero, without emitting any new event.

            if (this.eventFreezeCount < 0)
                this.eventFreezeCount = 0;
        },
        
        emitEvents: function() {
            if (this.eventFreezeCount != 0)
                return;
            for (var type in this.eventFreezeStack) {
                var data = this.eventFreezeStack[type];
                delete this.eventFreezeStack[type];
                this.emitEvent(type, data);
            }
        },
        
        emitEvent: function(type, data, merge) {
            if (this.eventFreezeCount > 0) {
                var old = this.eventFreezeStack[type] || [];
                if (merge) {
                    data = merge(old, data);
                }
                else {
                    for (var i=0 ; i < old.length ; i++)
                        if (data.indexOf(old[i]) == -1) data.push(old[i]);
                }
                this.eventFreezeStack[type] = data;
            }
            else {
                if (merge)
                    data = merge([], data);
                $(this).trigger('tree-changed', [data]);
            }
        },

        find: function(func, data, root) {
            function find_walk(func, node, data) {
                if (node.parent && func(node, data))
                    return node;
                for (var i=0 ; i < node.children.length ; i++) {
                    var result = find_walk(func, node.children[i], data);
                    if (result) return result;
                }
            }
            return find_walk(func, root || this.root, data) || null;
        },
        
        findAll: function(func, data, root) {
            var result = [];
            
            function findAll_walk(func, node, data) {
                if (node.parent && func(node, data))
                    result.push(node);
                for (var i=0 ; i < node.children.length ; i++)
                    findAll_walk(func, node.children[i], data);
            }
            findAll_walk(func, root || this.root, data);
            return result;
        },
        
        each: function(func, data, root) {
            function each_walk(func, node, data) {
                if (node.parent)
                    func(node, data);
                for (var i=0 ; i < node.children.length ; i++)
                    each_walk(func, node.children[i], data);
            }
            each_walk(func, root || this.root, data);
        },
        
        createSortFunction: function(column, direction, func) {
            direction = (direction == "desc" ? -1 : 1);
            
            if (this.root.children.length > 0) {
                var test = this.root.children[0].data[column];
                if (typeof test == "number")
                    return this.createSortFunctionForNumber(column, direction, func);
                else if (test && test.getTime)
                    return this.createSortFunctionForDate(column, direction, func);
                else
                    return this.createSortFunctionForString(column, direction, func);
            }
            
            // TODO: This should be a method that does some type checking at sort-time.
            return this.createSortFunctionForString(column, direction, func);
        },
        
        createSortFunctionForNumber: function(column, direction, func) {
            return function(a, b, data) {
                a = a.data[column] || 0;
                b = b.data[column] || 0;
                return direction * (a - b);
            };
        },

        createSortFunctionForDate: function(column, direction, func) {
            var noValue = new Date(0);
            return function(a, b, data) {
                a = a.data[column] || noValue;
                b = b.data[column] || noValue;
                return direction * (a.getTime() - b.getTime());
            };
        },

        createSortFunctionForString: function(column, direction, func) {
            var noValue = "";
            return function(a, b, data) {
                a = a.data[column] || noValue;
                b = b.data[column] || noValue;
                return direction * (a.toString().localeCompare(b.toString()));
            };
        }
    });

})(jQuery);
